Field of the Invention
The invention relates to the art of digital image processing, and to a method for compressing image data of a digitally produced or stored image to a reduced data set. Compression methods for image data are used in many fields of application of digital image processing so that, as a consequence of the reduced data set that results therefrom, storage space, data transmission time, processing time and resultant costs are reduced.
An important field of application is electronic reproduction technology, in which very large image data sets are processed. In reproduction technology, printing originals are produced for printed pages which contain all the page elements to be printed, such as texts, graphics and images. In the case of the electronic production of the printing originals, these elements are present in the form of digital data. The data are produced for an image, for example, by scanning the image in a scanner by point and line, decomposing each pixel into color components and digitizing the color values of these components. The data for texts and graphics are generally produced directly in a computer by text-processing and drawing programs. Depending upon the subsequently employed output process, for example outputting on a color printer or printing in a conventional printing machine, the data for the page elements are produced and stored in the color components of red, green and blue (RGB) or in the printing inks of four-color printing, specifically cyan, magenta, yellow and black (CMYK).
In the further operating sequence, the digitized texts, graphics and images are electronically assembled at a processing station under visual control on a color monitor or automatically in accordance with stored layout stipulations, i.e., the page elements are assembled, for example, in a storage area of the processing station in accordance with the layout to form a printed page. The finished printed page is converted, in this regard, into a data format suitable for outputting, and stored. The printed-page data for each of the printing inks (RGB or CMYK) are denoted as color separation data. The color separation data are used to produce printing plates for a conventional printing machine, or are transmitted directly to a fast color printer or to a digital printing machine and printed out thereat. For example, 24 pixels/mm (600 pixels/inch), constitute a sufficient resolution for the color separation data of the printed pages. If four color values are stored per pixel (CMYK), and the densities of the color values are digitized using 8 bits (=1 byte), respectively, the result for a printed page of size DIN A4 is a data set of 210 mmxc3x97297 mmxc3x9724xc3x9724xc3x974=143, 700, 480 bytes, (1) i.e., approximately 144 megabytes. This data set is further multiplied by the number of pages in a printed product. It is therefore necessary to process very large data sets in accordance with electronic reproduction technology. Consequently, an important role is played by methods for effectively compressing these data sets.
It is possible to distinguish areas having two types of image data on printed pages: firstly, areas containing a great many different colors changing from pixel to pixel, for example, scanned images, and secondly, areas containing only two colors, for example, text or graphics. Even in areas containing more than two colors, for example, colored graphics, there are frequently subareas with only two colors. Different compression methods have become known heretofore for the two types of image data, and they are optimized for the respective type, i.e., they attain a compression factor which is as high as possible, and do not at all or only slightly falsify the image information.
Methods of transformational coding have become known heretofore for compressing the image data in areas with many different colors. In this regard, the image data are divided into blocks of, for example, 8xc3x978 pixels, the blocks are transformed into a frequency representation (similar to the Fourier transformation) and only the frequency components relevant to the image information are stored in coded form. Such an expanded method is known by the designation JPEG (Joint Photographic Engineers Group) and has been internationally standardized.
The published European Patent Application EP-A-0 491 556 describes an extended transformation coding wherein image data blocks are additionally detected which have a uniform color, for example, the background color white. Such blocks are not subjected to transformational coding, but the positions thereof are coded with the aid of arithmetic coding, and inserted into the transformationally coded data of the remaining blocks. Moreover, an edge detector is used to detect pixels which are situated at the edges of graphic characters, and the color and position thereof are likewise coded by arithmetic coding.
Methods of run length coding wherein the position and the length-of-line sections with pixels of the same color are coded have become known heretofore for the purpose of compressing the image data in areas with two colors. There are run length codings which operate in one dimension and in two dimensions. In the case of the one-dimensional methods, pixels of the same color which are consecutive in a scanning line are counted, and these run lengths are stored as code words. In the case of the two-dimensional methods, the deviations of the run lengths in the current scanning line from the corresponding run lengths of the preceding scanning line are coded. For both types of run length coding, there are methods which are very widespread and standardized in facsimile transmission technology. A further method which is suitable for compressing image data with two colors has become known by the designation LZW (Lempel, Ziv, Welch). In this case, repeating sequences of pixels, which need not all be of the same color, are coded.
U.S. Pat. No. 5,267,333 describes a method for image data compression wherein images and partial images are sorted manually according to categories of text, background image and foreground image. Different compression methods are applied, respectively, for the three categories, both transformational codings and the standardized facsimile codings. The heretofore known methods for compressing image data with two colors have the disadvantage in that they cannot be combined in a simple manner with a transformational coding for image data with many colors. Moreover, the compression of the heretofore known methods for two-color image data is not effective enough in the case of the high resolutions which are used in electronic reproduction technology. Basically, the transformational coding could also be applied to the entire printed page. However, the compression factor then attainable in the two-color image areas would be low, and the decompressed image data would furthermore be affected by intolerable errors. Conversely, it would also be possible, for example, to apply the LZW method to the entire printed page. The attainable compression factor would then be low in the multicolor image areas.
It is therefore an object of the invention of the instant application to avoid the disadvantages of the heretoforeknown methods for compressing two-color image data by providing a method for compressing two-color image data without errors, which is effective and relatively easy to implement, and which is suitable for combination with a transformational coding for the purpose of compressing multicolor image data.
With the foregoing and other objects in view, there is provided, in accordance with the invention, a method for compressing digital image data present as a matrix of Mxc3x97N pixels, to a reduced data set, which comprises dividing the matrix of Mxc3x97N pixels into blocks of uxc3x97v pixels, classifying the blocks of uxc3x97v pixels into blocks containing only pixels of one block color or single-color blocks, blocks containing pixels of a foreground color and pixels of a background color or two-color blocks, and blocks containing pixels with more than two colors or multicolor blocks, and coding, in the image data of the single-color blocks and the two-color blocks, by command code words and data words, pixel patterns which are repeated in at least one manner selected from the group consisting of from block to block and within a block, respectively.
In accordance with another mode, the method invention includes coding consecutive single-color blocks with a like block color as that of run lengths.
In accordance with a further mode, the method invention includes coding the two-color blocks as bit patterns, assigning to each bit of the bit pattern a pixel of the two-color block, the bits of the bit pattern indicating whether the assigned pixel has one of the foreground color and the background color, respectively.
In accordance with an added mode, the method invention includes forming the bit pattern only with bits for the pixels of such lines of the two-color block, the distribution of foreground color and background color of which is different from the corresponding distribution in the preceding line of the two-color block.
In accordance with an additional mode, the method invention includes forming the bit pattern only with bits for a subset of undersampled pixels of the two-color block.
In accordance with yet another mode, the method invention includes coding consecutive two-color blocks with a like bit pattern as that of run lengths.
In accordance with yet a further mode, the method invention includes providing the single-color blocks in different regions of the image data with a different block color.
In accordance with yet an added mode, the method invention includes providing that the foreground color and the background color are different in different regions of the image data.
In accordance with yet an additional mode, the method invention includes coding as run lengths, consecutive multicolor blocks that are supposed to be skipped in the compression of the single-color blocks and the two-color blocks.
In accordance with still another mode, the method invention includes compressing the multicolor blocks by using a method of transformational coding.
In accordance with still a further mode, the method invention includes avoiding compression of the multicolor blocks.
In accordance with still an added mode, the method invention includes replacing a portion of the pixels in a multicolor block by the background color, and then coding the block like a two-color block.
In accordance with still an additional mode, the method invention includes replacing a portion of the pixels in a multicolor block by an arbitrary color, and then coding the block like a multicolor block.
In accordance with a concomitant mode, the method invention includes coding one of the properties of transparency and nontransparency, respectively, for the background color.
Other features which are considered as characteristic for the invention are set forth in the appended claims.
Although the invention is illustrated and described herein as embodied in a method for image data compression for two-color images, it is nevertheless not intended to be limited to the details shown, since various modifications and structural changes may be made therein without departing from the spirit of the invention and within the scope and range of equivalents of the claims.